/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.greedy;

/**
 * <p>
 * 蛙跳， 给定一维非负数组，每个元素代表从该位置能跳的最远位置，假设初始位置在第一个元素，判断输入数组是否能跳到末尾。
 *  A = [2,3,1,1,4], return true.
 *  A = [3,2,1,0,4], return false.
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class JumpGame {

   public boolean canJump(int[] nums) {
        if(nums==null || nums.length<=1){
            return true;
        }
        int len = nums.length;
        //使用两个指针，一个扫描当前值，一个扫描当前最远位置
        int i;
        int curMax = 0;
        for(i=0;i<len;i++){
            //当前最远位置不向后移的话，认为没有希望到达终点
            if(nums[i]==0 && curMax<i+1){
                return false;
            }
            if(nums[i]+i>curMax && nums[i]>0){
                //移动当前最远目的地
                curMax = i+ nums[i];
                //如果能到达，返回
                if(curMax>=len-1){
                    return true;
                }
            }
        }
        return false;
    }
}
